#include "list.h"
#include <stdio.h>
#include <malloc.h>

struct list_group_s {
    int max;
    int list_count;

    int* next;
    int* prev;
    int* free_heap; //+1 to make my life easier
    int heap_size;
    threadList** types;
};

struct list_s {
    int head;
    int size;
    list_group* group;
};

void closeListGroup(list_group* l) {
    if (l == NULL)
        return;
    free(l->prev);
    free(l->next);
    free(l->free_heap);
    free(l->types);
    free(l);
}

int initListGroup(list_group** ll, int size) {
    int i;
    list_group* l = NULL;
    l = (list_group*) malloc(sizeof (struct list_group_s));
    if (l == NULL)
        return -1;
    if (size < 1)
        size = 1;
    l->max = size;

    //allocate memory

    l->types = NULL;
    l->types = (threadList**) malloc(sizeof (threadList*) * size);
    if (l->types == NULL){
        closeListGroup(l);
        return -1;
    }

    size *= sizeof (int);

    l->next = NULL;
    l->next = (int*) malloc(size);
    if (l->next == NULL){
        closeListGroup(l);
        return -1;
    }

    l->prev = NULL;
    l->prev = (int*) malloc(size);
    if (l->prev == NULL){
        closeListGroup(l);
        return -1;
    }

    l->free_heap = NULL;
    l->free_heap = (int*) malloc(size + sizeof (int));
    if (l->free_heap == NULL){
        closeListGroup(l);
        return -1;
    }
    //initialize the free_threads heap and types array
    size = l->max;
    for (i = 0; i < size; i++) {
        l->types[i] = NULL;
        l->free_heap[i] = i - 1;
    }
    l->free_heap[size] = size-1;
    l->heap_size = size;

    l->list_count = 0;

    *ll = l;
    return 0;
}

void closeList(threadList* l) {
    l->group->list_count--;
    free(l);
}

int createNewList(list_group* group, threadList** l) {
    threadList* temp = NULL;
    temp = (threadList*) malloc(sizeof (struct list_s));
    if (temp == NULL)
        return -1;
    temp->head = -1;
    temp->size = 0;
    temp->group = group;
    group->list_count++;
    *l = temp;
    return 0;
}

void add_to_heap(list_group* threadList, int number) {
    int index = threadList->heap_size++;
    int index2, temp;
    int* heap = threadList->free_heap;

    heap[index] = number;
    index2 = index / 2;
    //heap[0]=-1 < heap[n] for all n>0
    while (heap[index] < heap[index2]) {
        temp = heap[index];
        heap[index] = heap[index2];
        heap[index2] = temp;
        index = index2;
        index2 = index / 2;
    }
}

int remove_from_heap(list_group* l) {
    int size = --l->heap_size;
    int index, index2, temp;
    int* heap = l->free_heap;
    int result = heap[1];
    heap[1] = heap[size+1];
    index = 1;
    index2 = 2;
    while (index2 + 1 < size) {
        if (heap[index2] > heap[index2 + 1]) {
            index2++;
        }
        if (heap[index2] < heap[index]) {
            temp = heap[index];
            heap[index] = heap[index2];
            heap[index2] = temp;
            index = index2;
        } else
            break;
        index = index2;
        index2 *= 2;
    }
    if (index2 < size) {
        if (heap[index2] < heap[index]) {
            temp = heap[index];
            heap[index] = heap[index2];
            heap[index2] = temp;
        }
    }
    return result;
}

int createNewElement(list_group* group) {
    int index;
    if (group->heap_size == 0)
        return -1;
    index = remove_from_heap(group);
    return index;
}

int removeFromList(threadList* l, int index) {
    list_group* threadList = l->group;
    int prev_index = threadList->prev[index];
    int next_index = threadList->next[index];
    if (threadList->types[index] != l)
        return -1; //doesn't belong to this threadList
    threadList->next[prev_index] = next_index;
    threadList->prev[next_index] = prev_index;
    if (index == l->head) {
        if (next_index != index)
            l->head = next_index;
        else
            l->head = EMPTY_LIST;
    }
    l->size--;
    threadList->types[index] = NULL;
    return 0;
}

int removeNodeList(threadList* l, int index) {
    if (removeFromList(l, index) == 0) {
        add_to_heap(l->group, index);
        return 0;
    }
    return -1;
}

void addTailList(threadList* l, int index) {
    list_group* threadList = l->group;
    int current = l->head;
    if (current == EMPTY_LIST) {
        l->head = index;
        threadList->next[index] = index;
        threadList->prev[index] = index;
        l->size = 1;
    } else {
        int prev_index = threadList->prev[current];
        int next_index = current;
        threadList->next[prev_index] = index;
        threadList->prev[next_index] = index;
        threadList->next[index] = next_index;
        threadList->prev[index] = prev_index;
        l->size++;
    }
    threadList->types[index] = l;
}

void addHeadList(threadList* l, int index) {
    list_group* threadList = l->group;
    int current = l->head;
    if (current == EMPTY_LIST) {
        l->head = index;
        threadList->next[index] = index;
        threadList->prev[index] = index;
        l->size = 1;
    } else {
        int prev_index = current;
        int next_index = threadList->next[current];
        threadList->next[prev_index] = index;
        threadList->prev[next_index] = index;
        threadList->next[index] = next_index;
        threadList->prev[index] = prev_index;
        l->size++;
    }
    threadList->types[index] = l;
    l->head = l->group->prev[index];
}

void addOrderedToList(threadList* l, int index) {
    int head = l->head;
    int i;
    list_group* group = l->group;
    if (l->head == EMPTY_LIST) {
        addTailList(l, index);
        return;
    }
    if (group->types[index] == l)
        return;
    for (i = index - 1; i >= 0; i--) {
        if (l->group->types[i] == l) {
            l->head = i;
            addHeadList(l, index);
            l->head = head;
            return;
        }
    }
    for (i = group->max - 1; i > index; i--) {
        if (l->group->types[i] == l) {
            l->head = i;
            addHeadList(l, index);
            l->head = head;
            return;
        }
    }
}

void move_element(threadList* from, threadList* to, int index) {
    removeFromList(from, index);
    addTailList(to, index);
}

void print_list(threadList* l) {
    int index = l->head;
    if (index == EMPTY_LIST) {
        printf("empty\n");
        return;
    }
    printf("%d ", index);
    index = l->group->next[index];
    while (index != l->head) {
        printf("%d ", index);
        index = l->group->next[index];
    }
    printf(" .\n");
}

int get_list_size(threadList* l) {
    return l->size;
}

int get_list_free_size(list_group* l) {
    return l->heap_size;
}

int get_element(threadList* l) {
    return l->head;
}

int next_element(threadList* l) {
    if (l->head != EMPTY_LIST)
        l->head = l->group->next[l->head];
    return l->head;
}

int previous_element(threadList* l){
    if (l->head != EMPTY_LIST)
        l->head = l->group->prev[l->head];
    return l->head;
}

threadList* get_list(list_group* group, int index) {
    return group->types[index];
}
